/*
 * Author: Rico
 *
*/

#include "sglLkdListBscOps.h"

Node* _creatNode(DataType nodeData) {
    Node *node = malloc(sizeof(Node));
    assert(node != NULL);
    node->data = nodeData;
    node->link = NULL;

    return node;
}

void initList(LinkedList *list) {
    list->first = list->last = malloc(sizeof(Node));
    assert(list->first != NULL);
    list->first->link = NULL;
    list->lenth = 0;
}

short isEmpty(LinkedList *list) {
    if (list->lenth == 0) {
        return 0;
    }
    return -1;
}

// case 1
void displayList(LinkedList *list) {
    if (isEmpty(list) == 0) {
        printf("Nothing to do with an empty list.\n");
        return;
    }

    Node *tmpNode = list->first->link;
    while (tmpNode != list->last) {
        printf("%d -- ", tmpNode->data);
        tmpNode = tmpNode->link;
    }
    printf("%d.\n", list->last->data);
}

// case 2
short insertAtTheEnd(LinkedList *list, DataType insertData) {
    // Node *newNode = malloc(sizeof(Node));
    // assert(newNode != NULL);
    // newNode->data = insertData;
    // newNode->link = NULL;
    Node *newNode = _creatNode(insertData);

    list->last->link = newNode;
    list->last = newNode;
    list->lenth++;

    return 0;
}

// case 3
short insertAtTheBeginning(LinkedList *list, DataType insertData) {
    // Node *newNode = malloc(sizeof(Node));
    // assert(newNode != NULL);
    // newNode->data = insertData;
    Node *newNode = _creatNode(insertData);
    newNode->link = list->first->link;

    list->first->link = newNode;
    list->lenth++;

    if (list->lenth == 1) {
        list->last = newNode;
    }

    return 0;
}

// case 4
short insertToOrderedList(LinkedList *list, DataType insertData) {
    // Node *newNode = malloc(sizeof(Node));
    // assert(newNode != NULL);
    // newNode->data = insertData;
    // newNode->link = NULL;
    Node *newNode = _creatNode(insertData);

    Node *tmpNode = list->first;
    while (tmpNode->link != NULL && tmpNode->link->data < insertData) {
        tmpNode = tmpNode->link;
        if (tmpNode->link == NULL) {
            tmpNode->link = newNode;
            list->last = newNode;
            list->lenth++;
            return 0;
        }
    }

    newNode->link = tmpNode->link;
    tmpNode->link = newNode;
    list->lenth++;

    return 0;
}

// case 5
short getLenth(LinkedList list) {
    return list.lenth;
}

// case 6
Node* findInList(LinkedList *list, DataType findData) {
    Node *tmpNode = list->first->link;
    while (tmpNode != NULL && tmpNode->data != findData) {
        tmpNode = tmpNode->link;
    }

    return tmpNode;
}

// case 7
short deleteLastData(LinkedList *list) {
    if (isEmpty(list) == 0) {
        return -1;
    }

    // tmpNode 作用是找到倒数第二个结点
    Node *tmpNode = list->first;
    while (tmpNode->link != list->last) {
        tmpNode = tmpNode->link;
    }

    free(list->last);
    list->last = tmpNode;
    list->last->link = NULL;
    list->lenth--;

    return 0;
}

// case 8
short deleteFirstData(LinkedList *list) {
    if (isEmpty(list) == 0) {
        return -1;
    }

    Node *tmpNode = list->first->link;
    list->first->link = tmpNode->link;
    free(tmpNode);
    list->lenth--;
    
    if (list->lenth == 0) {
        list->last = list->first;
    }

    return 0;
}

// case 9
short deleteByData(LinkedList *list, DataType deleteData) {
    Node *tmpNode = findInList(list, deleteData);
    if (tmpNode == NULL) {
        return -1;
    } else if (tmpNode == list->last) {
        deleteLastData(list);
        return 0;
    }

    // 避免回去找前驱, 将下一个结点的数据和链接复制
    // 到当前要删除的结点, 然后删除下一个结点即可
    Node *tmpNodeNext = tmpNode->link;
    tmpNode->data = tmpNodeNext->data;
    tmpNode->link = tmpNodeNext->link;
    free(tmpNodeNext);
    list->lenth--;

    return 0;
}

// case 10
short sortList(LinkedList *list) {
    if (isEmpty(list) == 0) {
        return -1;
    } else if (list->lenth == 1) {
        return 0;
    }

    // 将首结点之后的结点断开, 暂时另作一个链表
    Node *breakList = list->first->link->link;
    list->last = list->first->link;
    list->last->link = NULL;

    while (breakList != NULL) {
        // 断开的链表再挨个断开结点往原链表中插入
        Node *insertNode = breakList;
        breakList = breakList->link;

        // 把断开的结点按之前的排序插入方法插入
        Node *tmpNode = list->first;
        while (tmpNode->link != NULL && tmpNode->link->data < insertNode->data) {
            tmpNode = tmpNode->link;
        }
        if (tmpNode->link == NULL) {
            list->last = insertNode;
        }
        insertNode->link = tmpNode->link;
        tmpNode->link = insertNode;
    }

    return 0;
}

// case 11
short reverseList(LinkedList *list) {
    if (isEmpty(list) == 0) {
        return -1;
    } else if (list->lenth == 1) {
        return 0;
    }

    // 将首结点之后的结点断开, 暂时另作一个链表
    Node *breakNode = list->first->link->link;
    list->last = list->first->link;
    list->last->link = NULL;

    while (breakNode != NULL) {
        // 断开的链表再挨个断开结点
        Node *insertNode = breakNode;
        breakNode = breakNode->link;

        // 用头插的方式重新回到原链表中
        insertNode->link = list->first->link;
        list->first->link = insertNode;
    }

    return 0;
}

// case 12
short clearList(LinkedList *list) {
    if (isEmpty(list) == 0) {
        return -1;
    }

    Node *tmpNode = list->first->link;

    while (tmpNode != NULL) {
        list->first->link = tmpNode->link;
        free(tmpNode);
        tmpNode = list->first->link;
    }

    list->last = list->first;
    list->lenth = 0;

    return 0;
}

// case 13
void destroyList(LinkedList *list) {
    clearList(list);
    free(list->first);
    list->first = list->last = NULL;
}